package code.oldCode.feishuSpecializedTraining.binary_tree;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class MyBinaryTree3 {
    // 222. 完全二叉树的节点个数
    public int countNodes(TreeNode root) {
        // 低于O(n)的方法 O(logn * logn)
        // 先求树高
        int h = 0;
        TreeNode node = root;
        while (node != null) {
            node = node.left;
            h++;
        }
        // 最后一层有 1~2^(h-1) 个节点。总计有 2^(h-1)~2^h-1 个节点。
        // 类似二分查找的方法找位置：以h=4为例，第四层是8-15，8是1000，左左左，15是1111，右右右
        int left = (int) Math.pow(2, h - 1);
        int right = (int) Math.pow(2, h) - 1;
        while (left < right) {
            // 因为下面有left = mid，所以循环条件不能是left<=right，mid也要选靠右的（不能把mid取到left），否则可能无限循环
            int mid = (right - left + 1) / 2 + left;
            if (isExist(root, mid, h)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    public boolean isExist(TreeNode root, int pos, int h) {
        int compare = 1 << (h - 2);
        TreeNode node = root;
        while (node != null && compare > 0) {
            if ((compare & pos) == 0)
                node = node.left;
            else
                node = node.right;
            compare >>= 1;
        }
        return node != null;
    }

    // 110. 平衡二叉树
    boolean isBa = true;

    public boolean isBalanced(TreeNode root) {
        isBalancedDFS(root, 1);
        return isBa;
    }

    public int isBalancedDFS(TreeNode root, int depth) {
        if (root == null)
            return depth;
        int leftDepth = isBalancedDFS(root.left, depth + 1);
        int rightDepth = isBalancedDFS(root.right, depth + 1);
        if (Math.abs(rightDepth - leftDepth) > 1)
            isBa = false;
        return Math.max(leftDepth, rightDepth);
    }

    // 257. 二叉树的所有路径
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> stringList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        getString(root, sb, stringList);
        return stringList;
    }

    public void getString(TreeNode root, StringBuilder sb, List<String> stringList) {
        if (root.left == null && root.right == null) {
            stringList.add(sb.toString());
            return;
        }
        if (root.left != null) {
            sb.append("->").append(root.left.val);
            getString(root.left, sb, stringList);
            int numLen = String.valueOf(root.left.val).length();
            sb.delete(sb.length() - numLen - 2, sb.length());
        }
        if (root.right != null) {
            sb.append("->").append(root.right.val);
            getString(root.right, sb, stringList);
            int numLen = String.valueOf(root.right.val).length();
            sb.delete(sb.length() - numLen - 2, sb.length());
        }
    }
}
